package com.explorati.LeetCode347.topKFrequent;

import java.util.*;

/**
 @ Author : Weijian_Wang
 * @ Date : Created in 23:08 2021/12/7 9:49
 * @ Description ：
 */
public class Solution {

    /**
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     *
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     *
     * 输入: nums = [1], k = 1
     * 输出: [1]
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        //记录返回值，最大的两个数  此方法行不通：由于比较的是频率，返回的是值(需要用数组)
        int[] arr = new int[k];
        int i = 0;
        for(Map.Entry entry : map.entrySet()) {
            if(i < k) {
                arr[i] = (int) entry.getKey();
                i ++;
            } else {
                Arrays.sort(arr);
                if(map.get(arr[k - 1]) < (int)entry.getValue()) {
                    arr[k - 1] = (int) entry.getKey();
                }
            }
        }

        return arr;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,2,5,3,5,3,1,1,3};
        int k = 2;
        Solution solution = new Solution();

        int[] solutions = solution.topKFrequent(nums, k);
        for(int num : solutions) {
            System.out.println(num);
        }
    }
}
